COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00008 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a21.tex[106,phy] \today\hfill}

\bigskip
\line{{\bf Case Study: Knight's Move Driver} [assumes arrays]\hfill}
\smallskip
\line{\it ``To the Chess Club, Driver, and Don't Spare the Horses''\hfil}

\bigskip
In the game of chess, the knight moves two squares horizontally or vertically,
and one square at right angles.
This driver will execute command $S$ with $(R,F)$ set at each coordinate
pair which is a legal knight's move from the given pair $(RR,FF)$:

\smallskip
{\obeylines\obeyspaces\let =\ \tt
        FOR R:=RR-2 TO RR+2 DO
           IF (0<R) AND (R<9) THEN
              FOR F:=FF-2 TO FF+2 DO
                 IF (0<F) AND (F<9)
                    AND SQR(R-RR)+SQR(F-FF)=5 THEN
                       S
}

\smallskip\noindent
To test it, use this stub for $S$:

\smallskip
{\obeylines\obeyspaces\let =\ \tt
        WRITELN(RR,FF,R,F)
}

\smallskip
{\rmn
{\narrower\smallskip\noindent
{\bf Exercise.} 

\noindent
Write a program that will

\medskip
\item{(1)} Read the rank and file numbers of a knight on the chessboard.
\item{(2)} 
Print the rank and file of every square to which the knight can move directly.
\item{(3)} 
Print the rank and file of every square to which the knight can move in
exactly two turns.
\item{(4)} 
Print the ranks and files of the squares which require the largest
number of moves for the knight to reach.

\smallskip
{\bf Hint:} (2), (3), and (4) can all be done by a single subalgorithm.
\smallskip}
}

{\rmn
{\narrower\smallskip\noindent
\noindent{\bf Exercise.} (Mazlak, Structured Problem Solving with Pascal.)
(Assumes arrays and discrete maximizing.)

\medskip
A {\sl knight's tour\/} is a route followed by the chess knight over the
board, starting from any square, that visits every square exactly once
and ends where it started.
$$\vbox{\offinterlineskip
\halign{&\strut#&\vrule#&\quad\hfil#&\quad\hfil#&\quad\hfil#%
&\quad\hfil#&\quad\hfil#&\quad\hfil#\quad&\vrule#\cr
\noalign{\hrule}
\omit&height2pt&&&&&&&\cr
&&35&14&$\underline{1}$&22&25&32&\cr
\omit&height2pt&&&&&&&\cr
&&2&23&34&31&8&21&\cr
\omit&height2pt&&&&&&&\cr
&&13&36&15&24&33&26&\cr
\omit&height2pt&&&&&&&\cr
&&16&3&30&9&20&7&\cr
\omit&height2pt&&&&&&&\cr
&&29&12&5&18&27&10&\cr
\omit&height2pt&&&&&&&\cr
&&4&17&28&11&6&19&\cr
\omit&height2pt&&&&&&&\cr
\noalign{\hrule}
}}$$

\line{\hfil A Knight's Tour on a $6\times 6$ Board\hfil}

\medskip\noindent
According to Mazlak, a algorithm can be designed that will 
find a Knight's tour on an $8\times 8$ board from any starting point
by always moving to the
(unused) square from which there are the fewest moves to unused squares.
In case of ties, choose the square from which the fewest squares are
reachable in two more moves. 
Write a program to try it.
\smallskip}
}

\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft September 10, 1984

\bye